package 力扣日常刷题.木22一月.第08天0116;

/**
 * @author 帅小伙
 * @date 2022/1/16
 * @description
 * https://leetcode-cn.com/problems/partition-array-for-maximum-sum/solution/fei-chang-hao-li-jie-de-dong-tai-gui-hua-w0wq/
 */
public class Demo11动态规划中等分隔数组得到最大和 {

    long res = 0;

    public int maxSumAfterPartitioning(int[] arr, int k) {
        int length = arr.length;
        int[] dp = new int[length];
        for (int i = 1; i <= k; i++) {
            dp[i - 1] = getMaxValue(arr, 0, i - 1) * i;
        }
        for (int i = k; i < length; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i] = Math.max(dp[i - j] + getMaxValue(arr, i - j + 1, i) * j, dp[i]);
            }
        }
        return dp[length - 1];
    }

     int getMaxValue(int[] arr, int start, int end) {
        int res = 0;
        for (int i = start; i <= end; i++) {
            res = Math.max(res, arr[i]);
        }
        return res;
    }


}
